import java.util.HashMap;
import java.util.HashSet;

// 全O(1)的数据结构
// 测试链接 : https://leetcode.cn/problems/all-oone-data-structure/
public class AllO1 {

    class AllOne {

        //设计一个桶结构
        class Bucket{
            public HashSet<String> set;
            public int cnt;
            public Bucket last;
            public Bucket next;

            public Bucket(String str, int c) {
                set = new HashSet<>();
                set.add(str);
                cnt = c;
            }
        }

        //在当前cur位置后插入一个pos桶
        public void insert(Bucket cur, Bucket pos) {
            pos.next = cur.next;
            pos.last = cur;

            cur.next.last = pos;
            cur.next = pos;
        }

        //删除当前cur位置的桶
        public void remove(Bucket cur){
            cur.next.last = cur.last;
            cur.last.next = cur.next;
        }

        public Bucket head;
        public Bucket tail;
        public HashMap<String,Bucket> map;

        public AllOne() {
            map = new HashMap<>();
            head = new Bucket("",0);
            tail = new Bucket("",Integer.MAX_VALUE);
            head.next = tail;
            tail.last = head;
        }

        public void inc(String key) {
            if(!map.containsKey(key)) {  //map里不存在，首次添加字符串
                if(head.next.cnt == 1){  //查看存不存在频率为1的桶
                    map.put(key,head.next);
                    head.next.set.add(key);
                }else {
                    Bucket bucket = new Bucket(key,1);
                    insert(head,bucket);
                    map.put(key,bucket);
                }
            }else{ //map里存在这个字符串
                Bucket bucket = map.get(key);  //拿到这个字符串所在桶的位置
                if(bucket.next.cnt == bucket.cnt + 1) { //该桶右边存在比自己大1的桶
                    map.put(key,bucket.next);
                    bucket.next.set.add(key);

                }else{  //右边不存在
                    Bucket newBucket = new Bucket(key,bucket.cnt+1);
                    insert(bucket,newBucket);
                    map.put(key,newBucket);
                }
                bucket.set.remove(key);
                if(bucket.set.isEmpty()){
                    remove(bucket);
                }
            }
        }

        public void dec(String key) { //该方法给的字符串必定存在
            Bucket bucket = map.get(key);  //拿到 桶
            int num = bucket.cnt;
            if(num == 1){
                map.remove(key);
            }else {
                if(bucket.last.cnt == num-1 ){ //左边存在小1的桶
                    bucket.last.set.add(key);
                    map.put(key,bucket.last);
                }else {                        //左边没有num-1的桶
                    Bucket newBucket = new Bucket(key,num-1);
                    insert(bucket.last,newBucket);
                    map.put(key,newBucket);
                }
            }

            bucket.set.remove(key);
            if(bucket.set.isEmpty()) {
                remove(bucket);
            }

        }

        public String getMaxKey() {
            return tail.last.set.iterator().next();
        }

        public String getMinKey() {
            return head.next.set.iterator().next();
        }
    }
}
